package com.simon.study.algorithm.zheda;

import lombok.NoArgsConstructor;

/**
 * <p>
 *
 * @author simon
 */
public class OpenAddrHash {

    int     capacity;
    int     size;

    Entry[] entries;

    public enum  Type{
        LEGAL, EMPTY, DISCARD
    }

    @NoArgsConstructor
    public static class Entry{
        Integer     data;
        Type        type = Type.EMPTY;

        public Entry(Integer data) {
            this.data = data;
        }

        public Entry(Integer data, Type type) {
            this.data = data;
            this.type = type;
        }
    }

    public OpenAddrHash(int capacity) {
        if( capacity < 16 ){ capacity = 16; }
        this.capacity = prime(capacity);

        this.entries = new Entry[this.capacity];
    }

    public int find(int item){
        int idx = hash(item), nidx = idx;
        int qc  = 0;
        while(entries[nidx].type != Type.EMPTY && entries[nidx].data != item){
            if((++qc % 2) == 1){
                nidx = idx + (qc+1)/2 * (qc+1)/2;
                while(capacity <= nidx){ nidx -= capacity; }
            }else{
                nidx = idx - (qc/2 * qc/2);
                while (nidx < 0){
                    nidx += capacity;
                }
            }
        }
        return nidx;
    }


    public boolean insert(int key){
        int idx = find(key);
        if(entries[idx].type != Type.LEGAL){
            Entry entry  = new Entry(key, Type.LEGAL);
            entries[idx] = entry;
            return true;
        }
        return false;
    }


    public int hash(int k){ return k % capacity; }



    public static int prime(int n){
        int p = (n % 2) == 1 ? n+2 : n+1;

        int i = 0;
        while( true ) {
            for (i = (int) Math.sqrt(p); i > 2; i--) {
                if ((p % i) == 0) { break; }
            }
            if( i== 2 ){ return p; }
        }
    }
}
